4、数的分解
题目 数的分解
思路分析
直接暴力的话 要算几十分钟
#include<bits/stdc++.h>
using namespace std;
bool check(string s){
if(count(s.begin(),s.end(),'2') || count(s.begin(),s.end(),'4'))
return true;
return false;
}
int main()
{
int a, b, c;
int cnt = 0;
for(a = 1; a < 2019; a++) {
int i = a;
string s = to_string(i);
if(check(s))
continue;
for(b = 1; b < 2019; b++) {
int j = b;
string s2 = to_string(j);
if(check(s2))
continue;
for(c = 1; c < 2019; c++) {
int k = c;
string s3 = to_string(k);
if(check(s3))
continue;
if(a!=b && a!=c && b!=c && a+b+c==2019){
cnt++;
cout<<a<<"+"<<b<<"+"<<c;
cout<<endl;
}
}
}
}
cout<<cnt/3<<endl;
return 0;
}
优化思路
确定前两个数 第三个数就也确定了（四平方和那题）
重复算同一种 三数不能相同 所以第二层可以从第一层的后一个开始
另外 0~2019 其实可以实现筛出来合法的数
只需要在这些合法的数里面做枚举即可
#include<bits/stdc++.h>
using namespace std;
bool check(int num){
string s=to_string(num);
if(count(s.begin(),s.end(),'2') || count(s.begin(),s.end(),'4'))
return false;
return true;
}
int main()
{
vector<int> valid;
for(int i=1;i<2019;i++){
if(check(i))
valid.push_back(i);
}
int a, b, c;
int cnt = 0;
int n=valid.size();
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
a=valid[i],b=valid[j];
c=2019-a-b;
if(c>b && find(valid.begin(),valid.end(),c)!= valid.end())
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
代码实现
#include<bits/stdc++.h>
using namespace std;
bool check(int num){
string s=to_string(num);
if(count(s.begin(),s.end(),'2') || count(s.begin(),s.end(),'4'))
return false;
return true;
}
int main()
{
// vector<int> valid;
// for(int i=1;i<2019;i++){
// if(check(i))
// valid.push_back(i);
// }
// int a, b, c;
// int cnt = 0;
// int n=valid.size();
// for(int i = 0; i < n; i++) {
// for(int j = i+1; j < n; j++) {
// a=valid[i],b=valid[j];
// c=2019-a-b;
// if(c>b && find(valid.begin(),valid.end(),c)!= valid.end())
// cnt++;
// }
// }
// cout<<cnt<<endl;
cout<<"40785";
return 0;
}
💬 评论